On-Request Urban Transport Parallel Optimization
Identifieur interne : 005419 ( Main/Exploration ); précédent : 005418; suivant : 005420On-Request Urban Transport Parallel Optimization
Auteurs : Arnaud Renard [France] ; Michaël Krajecki [France] ; Alain Bui [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Transport problems are generally rather complex. The number of temporal, material, social and economic constraints makes it difficult to solved it both in theory (the problem is NP-complet) and in practice. This paper presents a pick-up and delivery transportation problem with time window and heterogeneous fleet of vehicles. Its objective is to provide an efficient schedule for drivers and the best service for users with the lower cost. This paper will explain the methodology used to compute and optimise the driver schedule. The goal is to assign more than eight hundreds fares to about forty drivers using thirty vehicles. Constraints programming approach makes it possible to treat instantaneously the local insertion of one journey in an optimised way. This local insertion was simply solved by an engine of constraints resolution in 1996 [MS88]. In addition, this method allows also the local insertion of several transports which was used to implement a total optimization of the schedule as a multitude of local displacements of few transports. This method becomes too slow when it moves more and more transport to improve quality of the solution. In this paper, a parallel solution, based on PVM, is introduced and some interesting results are provided. It is now possible to manage the collaboration of independent optimization engines working with different parameters. Experimentally, this robust solution is most of the time able to provide the best known sequential result.
Url:
DOI: 10.1007/11553762_25
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000415
- to stream Istex, to step Curation: 000413
- to stream Istex, to step Checkpoint: 001272
- to stream Main, to step Merge: 005565
- to stream Main, to step Curation: 005419
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On-Request Urban Transport Parallel Optimization</title><author><name sortKey="Renard, Arnaud" sort="Renard, Arnaud" uniqKey="Renard A" first="Arnaud" last="Renard">Arnaud Renard</name></author><author><name sortKey="Krajecki, Michael" sort="Krajecki, Michael" uniqKey="Krajecki M" first="Michaël" last="Krajecki">Michaël Krajecki</name></author><author><name sortKey="Bui, Alain" sort="Bui, Alain" uniqKey="Bui A" first="Alain" last="Bui">Alain Bui</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:12A3A98979DCDFA9EA6D53DAD63CC1615CE4A67F</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/11553762_25</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-J4S47NPX-9/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000415</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000415</idno><idno type="wicri:Area/Istex/Curation">000413</idno><idno type="wicri:Area/Istex/Checkpoint">001272</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001272</idno><idno type="wicri:doubleKey">0302-9743:2006:Renard A:on:request:urban</idno><idno type="wicri:Area/Main/Merge">005565</idno><idno type="wicri:Area/Main/Curation">005419</idno><idno type="wicri:Area/Main/Exploration">005419</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On-Request Urban Transport Parallel Optimization</title><author><name sortKey="Renard, Arnaud" sort="Renard, Arnaud" uniqKey="Renard A" first="Arnaud" last="Renard">Arnaud Renard</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Département Mathématiques et Informatique, Moulin de la Housse, Université de Reims Champagne Ardenne, CreSTIC, BP 1039, F-51687, Reims Cedex 2</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Champagne-Ardenne</region><settlement type="city">Reims</settlement></placeName><orgName type="university">Université de Reims Champagne-Ardenne</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Krajecki, Michael" sort="Krajecki, Michael" uniqKey="Krajecki M" first="Michaël" last="Krajecki">Michaël Krajecki</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Département Mathématiques et Informatique, Moulin de la Housse, Université de Reims Champagne Ardenne, CreSTIC, BP 1039, F-51687, Reims Cedex 2</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Champagne-Ardenne</region><settlement type="city">Reims</settlement></placeName><orgName type="university">Université de Reims Champagne-Ardenne</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Bui, Alain" sort="Bui, Alain" uniqKey="Bui A" first="Alain" last="Bui">Alain Bui</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Département Mathématiques et Informatique, Moulin de la Housse, Université de Reims Champagne Ardenne, CreSTIC, BP 1039, F-51687, Reims Cedex 2</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Champagne-Ardenne</region><settlement type="city">Reims</settlement></placeName><orgName type="university">Université de Reims Champagne-Ardenne</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Transport problems are generally rather complex. The number of temporal, material, social and economic constraints makes it difficult to solved it both in theory (the problem is NP-complet) and in practice. This paper presents a pick-up and delivery transportation problem with time window and heterogeneous fleet of vehicles. Its objective is to provide an efficient schedule for drivers and the best service for users with the lower cost. This paper will explain the methodology used to compute and optimise the driver schedule. The goal is to assign more than eight hundreds fares to about forty drivers using thirty vehicles. Constraints programming approach makes it possible to treat instantaneously the local insertion of one journey in an optimised way. This local insertion was simply solved by an engine of constraints resolution in 1996 [MS88]. In addition, this method allows also the local insertion of several transports which was used to implement a total optimization of the schedule as a multitude of local displacements of few transports. This method becomes too slow when it moves more and more transport to improve quality of the solution. In this paper, a parallel solution, based on PVM, is introduced and some interesting results are provided. It is now possible to manage the collaboration of independent optimization engines working with different parameters. Experimentally, this robust solution is most of the time able to provide the best known sequential result.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Champagne-Ardenne</li><li>Grand Est</li></region><settlement><li>Reims</li></settlement><orgName><li>Université de Reims Champagne-Ardenne</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Renard, Arnaud" sort="Renard, Arnaud" uniqKey="Renard A" first="Arnaud" last="Renard">Arnaud Renard</name></region><name sortKey="Bui, Alain" sort="Bui, Alain" uniqKey="Bui A" first="Alain" last="Bui">Alain Bui</name><name sortKey="Bui, Alain" sort="Bui, Alain" uniqKey="Bui A" first="Alain" last="Bui">Alain Bui</name><name sortKey="Krajecki, Michael" sort="Krajecki, Michael" uniqKey="Krajecki M" first="Michaël" last="Krajecki">Michaël Krajecki</name><name sortKey="Krajecki, Michael" sort="Krajecki, Michael" uniqKey="Krajecki M" first="Michaël" last="Krajecki">Michaël Krajecki</name><name sortKey="Renard, Arnaud" sort="Renard, Arnaud" uniqKey="Renard A" first="Arnaud" last="Renard">Arnaud Renard</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005419 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005419 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:12A3A98979DCDFA9EA6D53DAD63CC1615CE4A67F
|texte= On-Request Urban Transport Parallel Optimization
}}
| This area was generated with Dilib version V0.6.33. |  |